UOJ Logo _infinityOI的博客

博客

OI板子-exKMP

2021-10-02 21:57:07 By _infinityOI

Z 函数

$Z[i]=lcp(S,S[i:])$。人话:$Z[i]=S$ 与 $S$ 的每一个后缀的 LCP 长度。

求法:从 $2$ 到 $n$ 枚举 $i$($Z[1]$ 特判),维护 $L,R$ 表示右端点最靠右的一组 z-box(即匹配)。

pic:https://cdn.luogu.com.cn/upload/image_hosting/teunm6vw.png

正常版本:
int Z[N];
void Z_function(char *s, int n){
    for(int i = 2, L = 1, R = 1; i <= n; ++ i){
        if(i <= R){
            if(Z[i-L+1] < R-i+1) Z[i] = Z[i-L+1];
            else {
                Z[i] = R-i+1;
                while(i+Z[i] <= n && s[Z[i]+1] == s[i+Z[i]]) ++ Z[i];
            }
        } else while(i+Z[i] <= n && s[Z[i]+1] == s[i+Z[i]]) ++ Z[i];
        if(i+Z[i]-1 > R) L = i, R = i+Z[i]-1;
    }
    Z[1] = n;
}

浓缩版本:
int Z[N];
void Z_function(char *s, int n){
    for(int i = 2, L = 1, R = 1; i <= n; ++ i){
        if(i <= R) Z[i] = min(Z[i-L+1], R-i+1);
        while(i+Z[i] <= n && s[Z[i]+1] == s[i+Z[i]]) ++ Z[i];
        if(i+Z[i]-1 > R) L = i, R = i+Z[i]-1;
    }
    Z[1] = n;
}

exKMP

求出 $t$ 与 $s$ 的每一个后缀的 LCP 长度数组 $P$。

与 Z 函数类似。

int P[N];
void exKMP(char *s, int n, char *t, int m){
    Z_function(t, m);
    for(int i = 1, L = 0, R = 0; i <= n; ++ i){//注意从 0 开始
        //正常版本
        if(i <= R){
            if(Z[i-L+1] < R-i+1) P[i] = Z[i-L+1];
            else {
                P[i] = R-i+1;
                while(i+P[i] <= n && t[P[i]+1] == s[i+P[i]]) ++ P[i];
            }
        } else while(i+P[i] <= n && t[P[i]+1] == s[i+P[i]]) ++ P[i];
        if(i+P[i]-1 > R) L = i, R = i+P[i]-1;
        //浓缩版本
        if(i <= R) P[i] = min(Z[i-L+1], R-i+1);
        while(i+P[i]<=n && t[P[i]+1] == s[i+P[i]]) ++ P[i];
        if(i+P[i]-1 > R) L = i, R = i+P[i]-1;
    }
}

评论

run
谢谢

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。